Nearly any nontrivial physical, hardware or software system has a dashboard continually observing the system variables, and updating various measurements. Such data analysis applications deal with dynamic data: data arrives over time, and there is a need to continually output the result of some analysis f on data seen thus far Dj for each time instant j. This challenges privacy of analysis because the same function is computed on several deltas of the data and the collection of these function values has more potential to leak information than even several queries to different portions of static data.
The notion of differential privacy was extended to address this challenge. In particular, studies of differential privacy with continual observation and analysis identified the problem of computing the running sum of a series of 0/1 updates as an important technical primitive, formulated differential privacy of computing these running sums, and presented upper and lower bounds on accuracy of ε-differentially private algorithms for computing running sums. It was shown that an additive accuracy of
  O  ⁢          ⁢      (                  1        ɛ            ⁢              log                  2          ⁢                                                    ⁢      T        )  with constant probability is possible for the running sums problem, and that Ω(log T) additive error was necessary to answer accurately all running sum queries for all time steps jε└1,T┘. The sums problem is a rich problem capable of capturing many analyses by applying suitable predicates to the data items that map them to 0/1.
Algorithms for tracking statistics on dynamic data while preserving privacy under continual observation have been shown. In particular, an algorithm for privacy under continual observation has been presented for the running sum problem. For any fixed time step, the algorithm achieves additive error of
  O  ⁢          ⁢      (                  1        ɛ            ⁢              log                  1.5          ⁢                                                    ⁢      T        )  with constant probability, where T is an upper bound on the maximum size of the input and is assumed to be known to the algorithm. Another continually private algorithm for the running sum problem does not need to be given an upper bound on input size, and uses a dyadic tree data structure. However, the additive error of the algorithm does grow as the size of the processed input grows: at a fixed time step j, it can guarantee an additive error of
  O  ⁢          ⁢      (                  1        ɛ            ⁢              log        1.5            ⁢                          ⁢      T        )  with constant probability, matching the bound of the former algorithm without the need to specify an explicit bound T.
A general transformation of a single output (pan-) private streaming algorithm that satisfies a monotonicity property to an algorithm that is (pan-) private under continual observation has also been presented. However, such a property is not satisfied by algorithms that provide accurate estimates of decayed sums. Furthermore, it has also been shown that functions that change their value by d at least k times for some input and don't change their value on update 0 cannot be approximated to within an additive factor better than O(kd) while satisfying privacy under continual observation.